/**********************************************************

@description:use queue and singlist
*File Name:binary_tree_level.c
*Author: ydx
*mail: yudongxiang93@163.com
*Create Time: Sat 26 Apr 2025 10:41:23 AM CST
**********************************************************/
#include<stdio.h>
#include<stdlib.h>
typedef struct tnode{
	char data;
	struct tnode* lchild;
	struct tnode* rchild;
}tnode;
typedef struct queue{
	void * data;
	struct queue* next;
}queue;
void enqueue(queue** q,void * data){
	if(!data)
		return;
	if(*q){
		queue* prev=*q;
	    queue* cur=(*q)->next;
		while(cur){
			prev=cur;
			cur=cur->next;
		}
		queue *qn=(queue*)malloc(sizeof(queue));
		if(!qn){
			printf("malloc qn failed\n");
			return;
		}
		qn->data=data;
		qn->next=NULL;
		prev->next=qn;

	}else{
		*q=(queue*)malloc(sizeof(queue));
		if(!(*q)){
			printf("malloc q failed\n");
			return;
		}
		(*q)->data=data;
		(*q)->next=NULL;
	}
}
void* dequeue(queue** q){
	void *ret=NULL;
	if(*q){
		ret=(*q)->data;
		*q=(*q)->next;
	}
	return ret;

}
typedef void (*visit)(tnode*);
void pn(tnode* n){
	if(n)
		printf("%c ",n->data);
}

void leveltraverse(tnode *t,queue **q,visit v){
	if(t){
		v(t);
		enqueue(q,t->lchild);
		enqueue(q,t->rchild);
		tnode *l=(tnode*)dequeue(q);
		leveltraverse(l,q,v);
		tnode *r=(tnode*)dequeue(q);
		leveltraverse(r,q,v);
	}
}

void createTree1(tnode **n,char*data,int* idx){
	char ch;
	ch=data[*idx];
	*idx+=1;
	if(ch == '#'){
		*n=NULL;		
	}else{
		*n=(tnode*)malloc(sizeof(tnode));
		(*n)->data=ch;
		createTree1(&(*n)->lchild,data,idx);
		createTree1(&(*n)->rchild,data,idx);
	}
}
int main(int argc,char ** argv){
	tnode *t;
	int index=0;
	queue *q=NULL;
	createTree1(&t,argv[1],&index);
	leveltraverse(t,&q,pn);
	printf("\n");
}
